package com.algorithm.linkedlist;

import java.util.*;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/1 7:02 下午
 */
public class MyLinkedList<AnyType> implements List<AnyType> {

    /**
     * 当前元素个数
     */
    private int size;
    /**
     * 头结点 是个空值节点 不算在元素个数中
     */
    private Node head;
    /**
     * 尾节点 是个空值节点 不算在元素个数中
     */
    private Node tail;
    /**
     * 变更次数
     */
    private long modCount;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    @Override
    public Iterator<AnyType> iterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Object[] toArray() {
        Object[] elements = new Object[size];
        Node current = head.next;
        for (int i = 0; i < size; i++) {
            elements[i] = current;
            current = current.next;
        }
        return elements;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        int maxSize = Math.min(a.length, size);
        Node current = head.next;
        for (int i = 0; i < maxSize; i++) {
            a[i] = (T) current.value;
            current = current.next;
        }
        return a;
    }


    @Override
    public boolean add(AnyType anyType) {
        tail.prev = tail.prev.next = new Node(anyType, tail.prev, tail);
        size++;
        modCount++;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        Node current = head.next;
        while (current.prev != null) {
            AnyType value = current.value;
            if (Objects.equals(o, value)) {
                doDelete(current);
                size--;
                modCount++;
                return true;
            }
            current = current.next;
        }
        return false;
    }

    private void doDelete(Node current) {
        // 前驱的 后驱指针 连接后驱
        current.prev.next = current.next;
        // 后驱的 前驱指针 连接前驱
        current.next.prev = current.prev;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!this.contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends AnyType> c) {
        for (AnyType anyType : c) {
            this.add(anyType);
        }
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends AnyType> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        for (Object o : c) {
            this.remove(o);
        }
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void clear() {
        head.prev = tail;
        tail.prev = head;
        size = 0;
    }

    @Override
    public AnyType get(int index) {
        Node node = findNode(index);
        return node == null ? null : node.value;
    }

    private Node findNode(int index) {
        if (index >= size) {
            return null;
        }
        Node current = this.head.next;
        for (int i = 0; i <= index; i++) {
            if (i != index) {
                current = current.next;
            } else {
                return current;
            }
        }
        return null;
    }

    @Override
    public AnyType set(int index, AnyType element) {
        Node node = findNode(index);
        if (node == null) {
            throw new ArrayIndexOutOfBoundsException();
        }
        AnyType old = node.value;
        node.value = element;
        modCount++;
        return old;
    }

    @Override
    public void add(int index, AnyType element) {
        Node node = findNode(index);
        if (node == null) {
            throw new ArrayIndexOutOfBoundsException();
        }
        node.prev = node.prev.next = new Node(element, node.prev, node);
        size++;
        modCount++;
    }

    @Override
    public AnyType remove(int index) {
        Node node = findNode(index);
        if (node == null) {
            throw new ArrayIndexOutOfBoundsException();
        }
        node.prev.next = node.prev;
        return node.value;
    }

    @Override
    public int indexOf(Object o) {
        Node current = head.next;
        int i = 0;
        while (current != tail) {
            AnyType value = current.value;
            if (Objects.equals(o, value)) {
                return i;
            }
            current = current.next;
            i++;
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        Node current = tail.prev;
        int i = 0;
        while (current != head) {
            AnyType value = current.value;
            if (Objects.equals(o, value)) {
                return i;
            }
            current = current.prev;
            i++;
        }
        return -1;
    }

    @Override
    public ListIterator<AnyType> listIterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public ListIterator<AnyType> listIterator(int index) {
        throw new UnsupportedOperationException();
    }

    @Override
    public List<AnyType> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException();
    }


    private class Node {
        /**
         * 链表元素
         */
        private AnyType value;
        /**
         * 前驱
         */
        private Node prev;
        /**
         * 后驱
         */
        private Node next;

        public AnyType getValue() {
            return value;
        }

        public void setValue(AnyType value) {
            this.value = value;
        }

        public Node getPrev() {
            return prev;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node(AnyType value, Node prev, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }



}
